Package edu.claflin.finder.algo.clustering

Class Walktrap

java.lang.Object

edu.claflin.finder.algo.Algorithm

edu.claflin.finder.algo.clustering.ClusteringAlgorithm

edu.claflin.finder.algo.clustering.Walktrap

All Implemented Interfaces:

Processable<Graph,Graph>

public class Walktrap
extends ClusteringAlgorithm

Walktrap Algorithm for Community Detection. Random walks from a Node in a community tend to stay in the same Node. Based on python's igraph library.

Author:

Cesar Martin and Adolfo Perera

See Also:

• Original Paper
• Original igraph implementation

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	Walktrap.MutualConnectionsRecord	Stores the delta sigmas between a Community C connected to community 1 or community 2.

Nested classes/interfaces inherited from class edu.claflin.finder.algo.Algorithm

Algorithm.GraphSortOrder

Field Summary

Fields

Modifier and Type	Field	Description
private HashMap<Integer,HashMap<Node,Double>>	Pv
private int	steps

Fields inherited from class edu.claflin.finder.algo.Algorithm

args, PROP_PROGRESS

Constructor Summary

Constructors

Constructor	Description
Walktrap(ArgumentsBundle args)

Method Summary

Modifier and Type	Method	Description
private HashMap<Node,Double>	cprobs(List<Node> C, Graph graph, List<Node> nList)	Get a probability vector for a community.
private double	delta_sigma(int C1index, int C2index, List<Node> nList, Communities cms)	Calculate delta sigma from communities C1 and C2 according to Section 4.2 Theorem 5 in the paper.
private double	distance(int i, int j, List<Node> nList)	Compute the distance between community i and community j.
private int	getDegree(Node n)	Get the Node degree.
private double	getWeight(Node n)	Get the Node weight.
private HashMap<Node,Double>	merge_probs(int i, int j, Communities cms)	Calculate the probability vectors of joining 2 communities.
ArrayList<Graph>	process(Graph graph)	Processes data.
private void	remove_node(HeapNodeWT info, PriorityQueue<HeapNodeWT> q)	Remove a HeapNode from the Queue.
String	toString()

Methods inherited from class edu.claflin.finder.algo.clustering.ClusteringAlgorithm

buildCommunityGraphs, isWeighted

Methods inherited from class edu.claflin.finder.algo.Algorithm

addPropertyChangeListener, cull, getGraphSortOrder, getMinNodeCount, getPartiteNumber, getWeightName, removePropertyChangeListener, setGraphSortOrder, setMinNodeCount, setPartiteNumber, setProgress, setWeightName, zeropad

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

steps

private int steps

Pv

private HashMap<Integer,HashMap<Node,Double>> Pv

Constructor Details

Walktrap

public Walktrap(ArgumentsBundle args)

Method Details

toString

public String toString()

Overrides:

toString in class Object

process

public ArrayList<Graph> process(Graph graph)

Description copied from interface: Processable

Processes data.

Parameters:

graph - the T type object to process.

Returns:

the S type object array produced by the processing.

remove_node

private void remove_node(HeapNodeWT info,
 PriorityQueue<HeapNodeWT> q)

Remove a HeapNode from the Queue.

Parameters:

info - the node to remove

q - the priority queue to remove from

delta_sigma

private double delta_sigma(int C1index,
 int C2index,
 List<Node> nList,
 Communities cms)

Calculate delta sigma from communities C1 and C2 according to Section 4.2 Theorem 5 in the paper.

Parameters:

C1index - the index of community C1 in the list

C2index - the index of community C2 in the list

nList - the sorted Node list

cms - the Communities

Returns:

the delta sigma between C1 and C2

getDegree

private int getDegree(Node n)

Get the Node degree. The algorithm counts the node itself as a degree.

Parameters:

n - the Node to get the degree of

Returns:

the degree of the Node counting itself

getWeight

private double getWeight(Node n)

Get the Node weight. The algorithm counts the node itself as having a weight of weight/degree.

Parameters:

n - the Node to get the weight of

Returns:

the weight of the Node counting its own

cprobs

private HashMap<Node,Double> cprobs(List<Node> C,
 Graph graph,
 List<Node> nList)

Get a probability vector for a community. The probabilities are of going from the community to all Nodes in a random walk of length steps instance variable. This is an adaptation of the int constructor of the Probabilities class in igraph master's walktrap_communities.cpp

Parameters:

C - the community

graph - the original graph

nList - the sorted list of Nodes

Returns:

the probability vector

merge_probs

private HashMap<Node,Double> merge_probs(int i,
 int j,
 Communities cms)

Calculate the probability vectors of joining 2 communities. Equation in section 4.4 of the paper (first bullet point). This is an adaptation of the 2 ints constructor of the Probabilities class in igraph master's walktrap_communities.cpp

Parameters:

i - index of community 1

j - index of community 2

cms - the Communities

Returns:

the new probability vector

distance

private double distance(int i,
 int j,
 List<Node> nList)

Compute the distance between community i and community j. This is an adaptation of the 2 ints constructor of the compute_distance of the Probabilities class in igraph master's walktrap_communities.cpp

Parameters:

i - index of community 1

j - index of community 2

nList - the sorted list of nodes

Returns:

the distance between the communities